#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    // 先获取链表的长度
    int getLen(ListNode* head){
        int len = 0;
        while (head)
        {
            head = head->next;
            len++;
        }
        return len;
        
    }
    // 分个链表
    // 如果链表的长度《=size就做任何的操作，直接返回一个空的节点
    // 如果链表的长度》= size，就把链表的size个节点分割出来，也就是断开连接，然后返回剩余链表的头节点
   ListNode* splitList(ListNode* head, int size){
        // 先找到next_head的前一个节点
        ListNode* cur = head;
        for (int i = 0; i < size - 1 && cur; i++)
        {
            // 当前节点指针向后移动
            cur = cur->next;
        }
        // 如果链表的长度小于size
        if (cur == nullptr || cur->next == nullptr)
        {
            return nullptr;
        }
        ListNode* next_head = cur->next;
        // 断开连接
        cur->next = nullptr;
        return next_head;  
   }
   // 合并两个有序链表，返回合并后的链表的头节点和尾节点
   pair<ListNode*, ListNode*> merge(ListNode* list1, ListNode* list2){
    // 使用一个哨兵节点简化代码逻辑
    ListNode dummy;
    ListNode* cur = &dummy;
    // 当两个链表都不为空的时候循环继续下去
    while (list1 && list2)
    {
        // 双指针，归并两个链表
        if (list1->val < list2->val)
        {
            cur->next = list1;// 把list1添加到链表尾部
            list1 = list1->next;
        }else{
            cur->next = list2;
            list2 = list2->next;
        }
        // 结果链表的指针向后移动
        cur = cur->next;
    }
    // 拼接剩余部分的链表
    cur->next = list1 ? list1 : list2;
    // 找到合并后链表的尾部节点
    while (cur->next)
    {
        cur = cur->next;
    }
    // 循环结束之后。cur就是合并后链表的尾部节点，直接返回出去
    return { dummy.next, cur};
    
   }
    ListNode* sortList(ListNode* head) {
       // 获取链表的长度
        int size = getLen(head);
        // 初始化一个哨兵节点，简化代码的操作
        ListNode dummy(0, head);
        // step是步长，也就是参与合并链表的长度
        for (int setp = 1; setp < size; setp*=2)
        {
            // 新的链表的结尾
            ListNode* new_list_tail = &dummy;
            // 每一轮循环的起始节点
            ListNode* cur = dummy.next;
            while (cur)
            {
                // 从cur开始，分割出两端长为step的链表
                ListNode* head1 = cur;
                ListNode* head2 = splitList(head1, setp);
                // 下一轮循环的其实节点
                cur = splitList(head2, setp);
                // 合并
                auto [head, tail] = merge(head1, head2);
                // 合并后的head
                new_list_tail->next = head;
                new_list_tail = tail;
            }
            
        }
        return dummy.next;
        
    }

};
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

ListNode* createList(int arr[], int n) {
    if (n == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* cur = head;
    for (int i = 1; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return head;
}
int main() {
    Solution sol;

    // Test Case 1: 空链表
    ListNode* head1 = nullptr;
    ListNode* res1 = sol.sortList(head1);
    printList(res1); // 输出：NULL

    // Test Case 2: 单个节点
    int arr2[] = {5};
    ListNode* head2 = createList(arr2, 1);
    ListNode* res2 = sol.sortList(head2);
    printList(res2); // 输出：5 -> NULL

    // Test Case 3: 正常链表
    int arr3[] = {4, 2, 1, 3};
    ListNode* head3 = createList(arr3, 4);
    ListNode* res3 = sol.sortList(head3);
    printList(res3); // 输出：1 -> 2 -> 3 -> 4 -> NULL

    // Test Case 4: 逆序链表
    int arr4[] = {5, 4, 3, 2, 1};
    ListNode* head4 = createList(arr4, 5);
    ListNode* res4 = sol.sortList(head4);
    printList(res4); // 输出：1 -> 2 -> 3 -> 4 -> 5 -> NULL

    // Test Case 5: 有重复元素
    int arr5[] = {3, 2, 1, 2, 3};
    ListNode* head5 = createList(arr5, 5);
    ListNode* res5 = sol.sortList(head5);
    printList(res5); // 输出：1 -> 2 -> 2 -> 3 -> 3 -> NULL

    return 0;
}